BPP là một trong những lớp lớn nhất của các bài toán thực tiễn, nghĩa là đa số các bài toán được quan tâm trong BPP đều có thuật toán ngẫu nhiên có thể thực thi nhanh chóng trên máy tính. Do đó, một hướng nghiên cứu quan trọng là xác định xem một bài toán hay một lớp các bài toán có nằm trong BPP. BPP chứa P là tập hợp các bài toán giải được trong thời gian đa thức trên máy Turing đơn định do máy Turing đơn định là trường hợp đặc biệt của máy Turing ngẫu nhiên.

Cho một bài toán thực tế, xác suất sai bằng 1/3 có thể là quá lớn, nhưng lựa chọn 1/3 trong định nghĩa là tùy ý. Nó có thể là bất kì một hằng số nào lớn hơn 0 và nhỏ hơn 1/2, và tập hợp BPP là không thay đổi. Nó thậm chí không cần là hằng số: lớp BPP là không đổi dù cho phép xác suất sai lên tới 1/2 − n−c hoặc nhỏ hơn 2−nc, trong đó c là hằng số nguyên bất kì, và n là kích thước dữ liệu vào. Ý tưởng chính là tuy mỗi lần thực thi thuật toán có thể có xác suất sai cao, nếu lặp lại nhiều lần thì xác suất đa số các lần thực thi là sai giảm theo hàm lũy thừa theo chặn Chernoff.[1] Do đó có thể thu được thuật toán với xác suất sai thấp bằng cách lặp đi lặp lại thuật toán cơ sở nhiều lần và chọn lời giải đa số.